# 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
#  单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
#  请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
#  说明：
#  输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
#  翻转后单词间应当仅用一个空格分隔。
#  翻转后的字符串中不应包含额外的空格。
#
#  示例 1：
# 输入：s = "the sky is blue"
# 输出："blue is sky the"
#
#  示例 2：
# 输入：s = "  hello world  "
# 输出："world hello"
# 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
#
#  示例 3：
# 输入：s = "a good   example"
# 输出："example good a"
# 解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
#
#  示例 4：
# 输入：s = "  Bob    Loves  Alice   "
# 输出："Alice Loves Bob"
#
#  示例 5：
# 输入：s = "Alice does not even like bob"
# 输出："bob like even not does Alice"
#
#  提示：
#  1 <= s.length <= 10⁴
#  s 包含英文大小写字母、数字和空格 ' '
#  s 中 至少存在一个 单词
import collections
import re


class Solution:
    def reverseWords2(self, s: str) -> str:
        """
        双端队列
        :param s:
        :return:
        """
        s = s.strip()  # 去掉首尾的所有空格
        myDeque, word = collections.deque(), []  # word用于暂存得到的单词
        for curChar in s:
            if curChar == ' ' and word:  # 当前的字符是' ' 并且 word 列表中有元素说明到了一个单词额结束, 就需要将整个单词插到deque的头部
                myDeque.appendleft(''.join(word))
                word.clear()  # 清空以便下一次
            elif curChar != ' ':  # 当前的字符不是' '说明没到一个单词额结束, 就需要将字符放入到word中
                word.append(curChar)
        myDeque.appendleft(''.join(word))  # 特殊处理最后一个单词
        return ' '.join(myDeque)

    def reverseWords1(self, s: str) -> str:
        """
        使用正则表达式进行切分
        然后将得到的list进行反转
        最后拼接
        :param s:
        :return:
        """
        words = re.split("\s+", s.strip())
        words.reverse()
        return " ".join(words)

    def reverseWords(self, s: str) -> str:
        return self.reverseWords2(s)


if __name__ == "__main__":
    # s = "a good   example"
    s = "  hello world  "

    print(Solution().reverseWords(s))
